package com.nowcoder.code.lcof;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class JZ59 {

    public static void main(String[] args) {
        System.out.println(new JZ59().maxInWindows(new int[]{2, 3, 4, 2, 6, 2, 5, 1}, 8));
    }

    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> list = new ArrayList<>();
        if (size == 0 || num.length == 0 || size > num.length) {
            return list;
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < size - 1; i++) {
            map.put(num[i], i);
            priorityQueue.add(num[i]);
        }
        for (int i = size - 1; i < num.length; i++) {
            map.put(num[i], i);
            priorityQueue.add(num[i]);
            while (map.get(priorityQueue.peek()) < (i - size + 1)) {
                priorityQueue.poll();
            }
            list.add(priorityQueue.peek());
        }

        return list;

    }

}
